package com.scheuk.euler;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.BitSet;

public class MathTools {

	/* Uses Euclid's algorithm which uses division algorithm
	 * in combination with the observation that the gcd of two
	 * numbers also divides their difference.
	 * Definition:	gcd(a, 0) = a
	 * 				gcd(a, b) = gcd(b, a mod b);
	 */
	public static long gcd(long a, long b) {
		while (b != 0) {
			long tmp = b;
			b = a % b;
			a = tmp;
		}
		return a;
	}
	
	public static long gcd(double a, double b) {
		return gcd((long)a, (long)b);
	}
	
	/* Find the least common multiple of two integers. The LCM
	 * is the smallest positive integer that is a multiple of 
	 * both a and b. 
	 * 
	 * Definition:	LCM(a, b) = m x a = n x b
	 * 
	 * This implies m and n are coprime
	 */
	public static long lcm(long x, long y) {
		return (x*y)/gcd(x, y);
	}
	
	public static long lcm(long x, long y, long z) {
		return lcm(x, lcm(y, z));
	}
	
	public static long lcm(double a, double b) {
		return lcm((long)a, (long)b);
	}
	
	/* Based on the sieve of Eratosthenes, it's a simple efficient
	 * algorithm for finding all prime numbers to up a specific
	 * integer (below 10 million or so).
	 * Borrowed from http://stackoverflow.com/questions/1042902/most-elegant-way-to-generate-prime-numbers/1043247#1043247
	 */
	public static BitSet computePrimes(int limit)
	{
	    final BitSet primes = new BitSet();
	    primes.set(0, false);
	    primes.set(1, false);
	    primes.set(2, limit, true);
	    for (int i = 0; i * i < limit; i++)
	    {
	        if (primes.get(i))
	        {
	            for (int j = i * i; j < limit; j += i)
	            {
	                primes.clear(j);
	            }
	        }
	    }
	    return primes;
	}
	
	//fibonocci with memorization
	static BigInteger fibMem(int n) {
		ArrayList<BigInteger> fibCache = new ArrayList<BigInteger>();
		
      fibCache.add(BigInteger.ZERO);
      fibCache.add(BigInteger.ONE);
		
        if (n >= fibCache.size()) {
            fibCache.add(n, fibMem(n-1).add(fibMem(n-2)));
        }
        return fibCache.get(n);
	 }
	
	public static boolean[] sieve(int maxNumber) {
        int sieveBound = maxNumber / 2 ;// Paul Beckett: corrected from (limit - 1) / 2;  
        boolean[] sieve = new boolean[sieveBound];  
        int crossLimit = (int) Math.floor(Math.sqrt(maxNumber));  
  
        for (int i = 1; i < crossLimit; i++) {  
            if (!sieve[i]) {  
                for (int j = 2 * i * (i + 1); j < sieveBound; j = j  
                        + (2 * i + 1)) {  
                    sieve[j] = true;  
                }  
            }  
        } 
        return sieve;
	}
	
	public static boolean isPrime(int a) {
		if (a%2 == 0) return false;
		double c = Math.sqrt(a);
		for (int i = 3; i < c; i+=2) {
			if (a%i == 0) return false;
		}
		return true;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {

		//System.out.println("gcd(1989, 867) = " + MathTools.findGCD(1989, 867)); // correct answer is 51
		//System.out.println("lcm(21, 15) = " + MathTools.findLCM(21, 15)); //correct answer is 42
		//System.out.println("lcm(8,9,10) = " + MathTools.findLCM(8,9,10));

	}

}
